package leetcodecompetition.S109;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-07-22-23:56
 * @Description: 1.0
 */
public class T6299 {
    public int numberOfWays(int n, int x) {
        int m = (int) Math.pow(n, (double) 1/x);
        int[][] dp = new int[n + 1][m + 2];
        for (int[] d : dp) {
            Arrays.fill(d, -1);
        }
        System.out.println(n+" "+m);
        return dp(n, 1, x, dp);
    }

    public int dp(int n, int m, int x, int[][] dp) {
        System.out.println(n+" "+m);
        if (n == 0) return 1;
        if (dp[n][m] != -1) return dp[n][m];
        int sum = 0;
        while (true) {
            int r = n - (int) Math.pow(m, x);
            if (r >= 0) sum += dp(r, m + 1, x, dp);
            else break;
            m++;
        }
        dp[n][m]=sum;
        return sum;
    }

    @Test
    public void test() {
        System.out.println(numberOfWays(6, 1));
    }
}
